package com.wsx.first.d;

import java.util.ArrayList;
import java.util.PriorityQueue;

/**
 * Created by wangshunxi on 2022/5/14.
 * e-mail: wsr12240512@163.com
 * phone: 13388071923
 */
public class Main0046 {
    public static void main(String[] args) {
        Main0046 main0046 = new Main0046();
        int[] ints = {4,5,1,6,2,7,3,8};
        main0046.GetLeastNumbers_Solution(ints, 4);
    }
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        //排除特殊情况 fast-template
        if(k == 0 || input.length == 0)
            return res;
        //大根堆
        PriorityQueue<Integer> q = new PriorityQueue<>((o1, o2)->o2.compareTo(o1));
        //构建一个k个大小的堆
        for(int i = 0; i < k; i++)
            q.offer(input[i]);
        for(int i = k; i < input.length; i++){
            //较小元素入堆
            if(q.peek() > input[i]){
                q.poll();
                q.offer(input[i]);
            }
        }
        //堆中元素取出入数组
        for(int i = 0; i < k; i++)
            res.add(q.poll());
        return res;
    }
}
